|
In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated. The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.〔Belaid Benhamou and Mohamed Reda Saidi ("Reasoning by dominance in Not-Equals binary constraint networks" ), Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathmatiques et d'Informatique, France.〕〔Freuder, E.C.: (Eliminating Interchangeable Values in Constraint Satisfaction Problems ). In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233〕 The interchangeability algorithm reduces the search space of backtracking search algorithms, thereby improving the efficiency of NP-Complete CSP problems.〔Assef Chmeiss and Lakhdar Sais ("About Neighborhood Substitutability in CSP's" ), University of Artrois, Franc In the meantime, you ce.〕 ==Definitions== ;Fully Interchangeable :A value a for variable v is fully interchangeable with value b if and only if every solution in which v = a remains a solution when b is substituted for a and vice versa.〔 ;Neighbourhood Interchangeable :A value a for variable v is neighbourhood interchangeable with value b if and only if for every constraint on v, the values compatible with v = a are exactly those compatible with v = b.〔 ;Fully Substitutable :A value a for variable v is fully substitutable with value b if and only if every solution in which v = a remains a solution when b is substituted for a (but not necessarily vice versa).〔 ;Dynamically Interchangeable :A value a for variable v is dynamically interchangeable for b with respect to a set A of variable assignments if and only if they are fully interchangeable in the subproblem induced by A.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interchangeability algorithm」の詳細全文を読む スポンサード リンク
|